Leetcode刷题记录(Java)

Problem 105 Construct Binary Tree from Preorder and Inorder Traversal

根据先序遍历和中序遍历的结果构建二叉树

主要思路:
根据先序遍历和中序遍历的性质对元素进行定位

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return helper(0,0,inorder.length-1,preorder,inorder);
    }
    public TreeNode helper(int preStart,int inStart,int inEnd,int[] preorder,int[] inorder){
        if (preStart>preorder.length-1||inStart>inEnd)
            return null;
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = 0;
        for (int i=inStart;i<=inEnd;i++){
            if (inorder[i]==root.val){
                inIndex = i;
            }
        }
        root.left = helper(preStart+1,inStart,inIndex-1,preorder,inorder);
        root.right = helper(preStart+inIndex-inStart+1,inIndex+1,inEnd,preorder,inorder);
        return root;
    }
}

代码说明:
以题目给出的先序遍历[3,9,20,15,7]和中序遍历[9,3,15,20,7]为例,在 helper 中先确定 root 的值,第一次进去就是先序的第一个值,也就是 3.然后的循环是为了找出当前这个 root 在中序遍历中的下标,比如本例中,inIndex=1,然后为 root 加上 left 和 right,left 就是先序遍历中 root 的右边结点,也就是 preStart+1,而右子树是右边 preStart+1+inIndex-inStart
左子树:root.left = helper(前序左子树范围,中序左子树范围,前序序列,中序序列)
右子树:root.right = helper(前序右子树范围,中序右子树范围,前序序列,中序序列)

Problem 106 Construct Binary Tree from Inorder and Postorder Traversal

根据先序遍历和后序遍历的结果构建二叉树

主要思路:
根据中序遍历和后序遍历的性质对元素进行定位

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (null == postorder || postorder.length < 1) {
            return null;
        }
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }

    public TreeNode buildTree(int[] inorder, int start, int end, int[] postorder, int idx) {
        if (start > end || idx < 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[idx]);
        int rIdx = start;
        for (; rIdx <= end; rIdx++) {
            if (inorder[rIdx] == postorder[idx]) {
                break;
            }
        }
        root.left = buildTree(inorder, start, rIdx - 1, postorder, idx - (end - rIdx) - 1);
        root.right = buildTree(inorder, rIdx + 1, end, postorder, idx - 1);
        return root;
    }
}

代码说明:
以中序[9,3,15,20,7]和后序[9,15,7,20,3]为例,根据性质,后序数组的最后一个元素自然是根节点,它左边那个元素自然是它的右子树,剩下的问题是确定左子树,左子树需要找到先序遍历中根节点的位置,然后取其左边元素

Problem 114 Flatten Binary Tree to Linked List

将二叉树转换成链表

主要思路:
可以考虑先将根节点的左子树全部压平再将右子树全部压平,最后将压平的左子树插入到右子树中

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if (root==null)
            return;
        if (root.left!=null)
            flatten(root.left);
        if (root.right!=null)
            flatten(root.right);
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = null;
        while (root.right!=null)
            root = root.right;
        root.right = temp;
    }
}

代码说明:
以题目中给定的树为例,最先运行到最左非叶子结点,在本例中为 2,保存 temp=4.然后将 root.left(3)当作 root.right,完成 2->3,并将 left 置为 null,随后就是 root 一直朝着右边移动,最后将最初存储的 temp 接在最后,完成左边 2->3->4,随后完成右边 1->5->6.最后一步就是合并,1->2->3->4->5->6

Problem 134 Gas Station

给定一个 gas 数组,一个 cost 数组,gas 数组是车在当前加油站能够补充的油,cost 数组是要从当前加油站移动到相邻加油站所需要消耗的油.如果能够从起点绕一圈回到起点,则返回起点下标.否则返回-1

代码实现:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0, sum = 0, start = 0;
        for (int i = 0; i < gas.length; ++i) {
            total += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (sum < 0) {
                start = i + 1;
                sum = 0;
            }
        }
        return (total < 0) ? -1 : start;
    }
}

代码说明:
这段代码主要要注意两个变量:一个是total,它用来记录总共能加的油是否比总共消耗的多,如果加的总数没有消耗的多,那么无论怎么走都无法绕一圈.另一个是sum,它用来记录从起点到当前结点的累计量.如果 sum 小于 0,代表着从起点到当前结点的累计加上当前结点的净消耗不足以让它离开,这说明这段内的所有结点都不适合当起点.那么将起点设为当前结点的下一个,而不需要从原先结点的下一个遍历.

Problem 139 Word Break

判断给出的字符串能否由数组中的字符串数组组成

主要思路:
本题利用动态规划的思想来解,每次取一个 s 的子序列,判断它是否在数组中,不断填充 dp 数组

代码实现:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s==null||s.length()==0)
            return false;
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i=1;i<=s.length();i++){
            for (int j=0;j<=i;j++){
                if (dp[j]&&wordDict.contains(s.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

代码说明:
以题中给出的例子 3 为例,dp[0]=1,然后开始取子序列,
i=1
j=0 dp[0]=true&&wordDict.contains(c)=false,不更新
j=1 dp[1]=false,不更新

i=2
j=0 dp[0]=true&&wordDict.contains(ca)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新

i=3
j=0 dp[0]=true&&wordDict.contains(cat)=true,dp[3]=true,break

i=4
j=0 dp[0]=true&&wordDict.contains(cats)=true,dp[4]=true,break

i=5
j=0 dp[0]=true&&wordDict.contains(catsa)=false,不更新
j=1 dp[1]=true&&wordDict.contains(atsa)=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=true&&wordDict.contains(sa)=false,不更新
j=4 dp[4]=true&&wordDict.contains(a)=false,不更新
j=5 dp[5]=false,不更新

i=6
j=0 dp[0]=true&&wordDict.contains(catsan)=false,不更新
j=1 dp[1]=true&&wordDict.contains(atsan)=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=true&&wordDict.contains(san)=false,不更新
j=4 dp[4]=true&&wordDict.contains(an)=false,不更新
j=5 dp[5]=false,不更新
j=6 dp[6]=false,不更新

i=7
j=0 dp[0]=true&&wordDict.contains(catsand)=false,不更新
j=1 dp[1]=true&&wordDict.contains(atsand)=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=true&&wordDict.contains(sand)=true,dp[7]=true,break

i=8
j=0 dp[0]=true&&wordDict.contains(catsando)=false,不更新
j=1 dp[1]=true&&wordDict.contains(atsando)=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=true&&wordDict.contains(sando)=false,不更新
j=4 dp[4]=true&&wordDict.contains(ando)=false,不更新
j=5 dp[5]=false,不更新
j=6 dp[6]=false,不更新
j=7 dp[7]=true&&wordDict.contains(o)=false,不更新
j=8 dp[8]=false,不更新

i=9
j=0 dp[0]=true&&wordDict.contains(catsandog)=false,不更新
j=1 dp[1]=true&&wordDict.contains(atsandog)=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=true&&wordDict.contains(sandog)=false,不更新
j=4 dp[4]=true&&wordDict.contains(andog)=false,不更新
j=5 dp[5]=false,不更新
j=6 dp[6]=false,不更新
j=7 dp[7]=true&&wordDict.contains(og)=false,不更新
j=8 dp[8]=false,不更新
j=9 dp[9]=false,不更新
结束,最后判断 dp[9]为 false,故无法组成

再以例子 1 为例
i=1
j=0 dp[0]=true&&wordDict.contains(l)=false,不更新
j=1 dp[1]=false,不更新

i=2
j=0 dp[0]=true&&wordDict.contains(le)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新

i=3
j=0 dp[0]=true&&wordDict.contains(lee)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=false,不更新

i=4
j=0 dp[0]=true&&wordDict.contains(leet)=true,dp[4]=true,break

i=5
j=0 dp[0]=true&&wordDict.contains(leetc)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=false,不更新
j=4 dp[4]=true&&wordDict.contains(c)=false,不更新
j=5 dp[5]=false,不更新

i=6
j=0 dp[0]=true&&wordDict.contains(leetco)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=false,不更新
j=4 dp[4]=true&&wordDict.contains(co)=false,不更新
j=5 dp[5]=false,不更新
j=6 dp[6]=false,不更新

i=7
j=0 dp[0]=true&&wordDict.contains(leetcod)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=false,不更新
j=4 dp[4]=true&&wordDict.contains(cod)=false,不更新
j=5 dp[5]=false,不更新
j=6 dp[6]=false,不更新
j=7 dp[7]=false,不更新

i=8
j=0 dp[0]=true&&wordDict.contains(leetcode)=false,不更新
j=1 dp[1]=false,不更新
j=2 dp[2]=false,不更新
j=3 dp[3]=false,不更新
j=4 dp[4]=true&&wordDict.contains(code)=true,dp[8]=true,break

结束,最后判断 dp[8]为 true,故可以组成

Problem 142 Linked List Cycle II

先判断链表有没有环,再判断环的入口在哪个结点

主要思路:
首先判断链表有没有环,可以使用快慢指针进行判断.因为如果有环,那么首先快指针不会指向 null,然后快指针每次都逼近慢指针 1 个单位.这样它们肯定会相遇.

然后根据上图判断环的入口,假设相遇点是 z,那么快指针走了 a+b+c+b 的距离,慢指针走了 a+b,由于快指针=2*慢指针,所以 a+b+c+b=2*(a+b)=>a=c,也就是说慢指针从头部重新走和快指针从相遇点继续走相遇的结点就是环的入口

代码实现:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode p = head;
        ListNode q = head;
        while(q.next != null && q.next.next != null){
            p = p.next;
            q = q.next.next;
            if(q == p){
                p = head;
                while(p != q){
                    p = p.next;
                    q = q.next;
                }
                return p;
            }
        }
        return null;
    }
}

Problem 143 Reorder List

对链表进行重排列

主要思路:

通过快慢指针定位链表中点
反转后半链表
将后半链表的元素按顺序插入到前半链表中

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null) return;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!= null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode reverseHead = reverse(slow.next);
        slow.next = null;
        ListNode currHead = head;
        while(reverseHead != null){
            ListNode firstNext = currHead.next;
            ListNode secondNext = reverseHead.next;
            currHead.next = reverseHead;
            reverseHead.next = firstNext;
            currHead = firstNext;
            reverseHead = secondNext;
        }
    }

    public ListNode reverse(ListNode head) {
        ListNode curr = head;
        ListNode prev = null;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Problem 148 Sort List

链表排序

主要思路:
题目要求时间复杂度 O(nlogn),那么可以考虑归并排序

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        return sort(head);
    }
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }
        while (left != null) {
            node.next = left;
            node = node.next;
            left = left.next;
        }
        while (right != null) {
            node.next = right;
            node = node.next;
            right = right.next;
        }
        return dummy.next;
    }

    private ListNode sort(ListNode head) {
        // 1 element
        if (head.next == null) {
            return head;
        }
        // 2 elements
        if (head.next.next == null) {
            if (head.val > head.next.val) {
                ListNode t = head;
                head = head.next;
                head.next = t;
                t.next = null;
            }
            return head;
        }
        // more elements
        ListNode slower = head, faster = head;
        while (faster != null && faster.next != null) {
            slower = slower.next;
            faster = faster.next.next;
        }
        ListNode slowerNext = slower.next;
        slower.next = null;
        return merge(sort(head), sort(slowerNext));
    }
}

代码说明:
代码看起来比较复杂,但是逻辑比较清晰.首先考虑 1 个元素和 2 个元素的情况.之后就是多个元素,归并排序是将链表分为左右两边.此时必然用到快慢指针.分好之后进行归并,归并时分别比较前半部分和后半部分第一个元素的大小,较小的插入到 dummy.next 中.然后移动较小那部分的指针以及 dummy 指针.依次比较,直到有一方排序结束

Problem 152 Maximum Product Subarray

求数组的最大子序列之积

代码实现:

class Solution {
    /**
     * 当遍历到一个正数时，此时的最大值等于之前的最大值乘以这个正数和当前正数中的较大值，此时的最小值等于之前的最小值乘以这个正数和当前正数中的较小值。
     * 当遍历到一个负数时，先用一个变量t保存之前的最大值 mx，然后此时的最大值等于之前最小值乘以这个负数和当前负数中的较大值，此时的最小值等于之前保存的最大值t乘以这个负数和当前负数中的较小值。
     * 在每遍历完一个数时，都要更新最终的最大值。
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        if (nums.length==1)
            return nums[0];
        int max = nums[0],min = nums[0],maxAns = nums[0];
        for (int i=1;i<nums.length;i++){
            int mx = max,mn = min;
            max = Math.max(Math.max(nums[i],mx*nums[i]),mn*nums[i]);
            min = Math.min(Math.min(nums[i],mx*nums[i]),mn*nums[i]);
            maxAns = Math.max(max,maxAns);
        }
        return maxAns;
    }
}

Problem 179 Largest Number

给定一个 int 数组,要求返回这些 int 能够组成的最大数字(由于数字可能会大到溢出,所以以字符串形式返回)

主要思路:
直接对数组排序,不过排序的规则是比较 a+b 和 b+a 的值谁比较大,比如 3 和 34,是组成 334 还是 343,自然是 343 比较大,所以 34 排在 3 前面

代码实现:

class Solution {
    public static String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) return "";
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (i, j) -> {
            String s1 = i+j;
            String s2 = j+i;
            return s2.compareTo(s1);
        });
        StringBuilder res = new StringBuilder();
        for (String str : strs) {
            res.append(str);
        }
        return res.charAt(0) =='0' ? "0": res.toString();
    }
}

Problem 207 Course Schedule

给定课程数目,以及一个二维数组,数组中的每个元素的第一个元素代表要上的课,第二个元素代表要上课之前需要上的前序课程,需要判断能否达到无环状态

主要思路:
实际上是个拓扑排序的题目,对每个结点初始化入度.当所有入度消失之后取出当前元素.

代码实现:

class Solution {
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        for (int[] pair:prerequisites)
            indegree[pair[0]]++;
        Queue<Integer> queue = new LinkedList<>();
        for (int i=0;i<indegree.length;i++){
            if (indegree[i]==0)
                queue.offer(i);
        }
        int size = queue.size();
        while (!queue.isEmpty()){
            int top = queue.remove();
            for (int[] prerequisite : prerequisites) {
                if (prerequisite[1] == top) {
                    indegree[prerequisite[0]]--;
                    if (indegree[prerequisite[0]] == 0) {
                        size++;
                        queue.add(prerequisite[0]);
                    }
                }
            }
        }
        return size==numCourses;
    }
}